# -*- coding: utf-8 -*-
"""
Set partition into lists

AUTHOR:

 - Ali Chouria
 - Olivier Mallet
 - Jean-Baptiste Priez
"""
#*****************************************************************************
#       Copyright (C) 2013 Ali Chouria <ali.chouria@univ-rouen.fr>,
#                          Olivier Mallet <olivier.mallet@univ-rouen.fr>,
#                          Jean-Baptiste Priez <jbp@kerios.fr>,
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from sage.structure.parent import Parent
from sage.rings.integer import Integer
from sage.misc.classcall_metaclass import ClasscallMetaclass
from sage.structure.unique_representation import UniqueRepresentation
from sage.sets.disjoint_union_enumerated_sets import \
    DisjointUnionEnumeratedSets
from sage.sets.non_negative_integers import NonNegativeIntegers
from sage.misc.lazy_attribute import lazy_attribute, lazy_class_attribute
from sage.structure.list_clone import ClonableArray
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.sets.family import Family
from sage.sets.set import Set
from sage.combinat.set_partition_ordered import OrderedSetPartitions
from sage.combinat.tools import transitive_ideal
from sage.misc.misc import uniq
from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets
from sage.combinat.permutation import Permutations
from sage.combinat.cartesian_product import CartesianProduct


class SetPartitionIntoList(ClonableArray):
    """
    The class of set partition into lists

    """
    __metaclass__ = ClasscallMetaclass

    @staticmethod
    def __classcall_private__(cls, *args, **opts):
        """
        """
        return cls._auto_parent.element_class(cls._auto_parent, *args, **opts)

    @lazy_class_attribute
    def _auto_parent(cls):
        """
        The automatic parent of the element of this class

        When calling the constructor of an element of this class, one needs a
        parent. This class attribute specifies which parent is used.

        EXAMPLES::

            sage: SetPartitionIntoList._auto_parent
            ....
            sage: SetPartitionIntoList().parent()
            ....
         """
        return SetPartitionIntoLists_all()

    def __init__(self, parent, li=None, check=True):
        """
        TESTS::

            sage: PackedWord([]).parent()
            Packed words
        """
        if li is None:
            li = []
        ClonableArray.__init__(self, parent, map(lambda x: tuple(x), li), check=check)

    def check(self):
        """
        Checks that ``self`` is a packed word

        TESTS::

            sage: PackedWord([3,3,2,1])
            [3, 3, 2, 1]

            #sage: PackedWord([2,2,1,0,4])
            #Traceback (most recent call last)
            #...
            #AssertionError: This is not a packed word
        """
        pass

    def is_empty(self):
        """
        Returns whether ``self`` is the empty word.

        EXAMPLES::

            sage: PackedWord().is_empty()
            True
            sage: PackedWord([]).is_empty()
            True
            sage: PackedWord([2,1,2]).is_empty()
            False
        """
        return not self

    def _latex_(self):
        """
        TESTS::

            sage: latex(PackedWord([1,2,3,1,1,3]))
            123113
            sage: latex(PackedWord(range(1,11)))
            [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
        """
        if max(self) >= 10:
            return str(list(self))
        return str(list(self)).replace(
            '[', '\\{').replace(
            ']', '\\}').replace(
            ', ', '')

    def size(self):
        """
        EXAMPLES::

            sage: PackedWord().size()
            0
            sage: PackedWord([2,1,1]).size()
            3
        """
        return reduce(
            lambda x, y: x + len(y),
            self, 0
        )


#==============================================================================
# Abstract class to serve as a Factory no instance are created
#==============================================================================
class SetPartitionIntoLists(UniqueRepresentation, Parent):
    """
    Factory class for packed words.

    INPUT:

    - ``size`` -- (optional) an integer

    OUTPUT:

    - the set of all packed words (of ``size`` (if specified))

    TESTS::

        sage: TestSuite(PackedWords()).run()

    EXAMPLES::

        sage: PackedWords()
        Packed words
        sage: PackedWords(4)
        Packed words of size 4
    """
    @staticmethod
    def __classcall_private__(cls, n=None):
        """
        TESTS::

            sage: from sage.combinat.packed_words import PackedWords_size, \
            ....:     PackedWords_all
            sage: isinstance(PackedWords(2), PackedWords)
            True
            sage: isinstance(PackedWords(), PackedWords)
            True
            sage: PackedWords(2) is PackedWords_size(2)
            True
            sage: PackedWords(5).cardinality()
            541
            sage: PackedWords() is PackedWords_all()
            True
        """
        if n is None:
            return SetPartitionIntoLists_all()
        else:
            assert(isinstance(n, (Integer, int)) and n >= 0), \
                "n must be a non negative integer"
            return SetPartitionIntoLists_size(Integer(n))


#==============================================================================
# Enumerated set of all packed words
#==============================================================================
class SetPartitionIntoLists_all(
        DisjointUnionEnumeratedSets, SetPartitionIntoLists):

    def __init__(self):
        """
        TESTS::

            sage: from sage.combinat.packed_words import PackedWords_all
            sage: P = PackedWords_all()
            sage: P.cardinality()
            +Infinity
            sage: it = iter(P)
            sage: (it.next(), it.next(), it.next(), it.next(), it.next())
            ([], [1], [1, 2], [2, 1], [1, 1])
            sage: it.next().parent()
            Packed words
            sage: P([])
            []
            sage: P is PackedWords_all()
            True
            sage: TestSuite(P).run()
        """
        Parent.__init__(self, category=InfiniteEnumeratedSets())
        DisjointUnionEnumeratedSets.__init__(
            self, Family(NonNegativeIntegers(), SetPartitionIntoLists_size),
            facade=True, keepkey=False)

    def _repr_(self):
        """
        TESTS::

            sage: PackedWords()
            Packed words
        """
        return "Set partition into list"

    def __contains__(self, w):
        """
        TESTS::

            sage: P = PackedWords()
            sage: 1 in P
            False
            sage: PackedWord([]) in P
            True
            sage: [1,1,4,2,3] in P
            True

        """
        if isinstance(w, self.element_class):
            return True
        try:
            self(w)
            return True
        except:
            return False

    def __call__(self, x=None, *args, **keywords):
        """
        Ensure that ``None`` instead of ``0`` is passed by default.

        TESTS::

            sage: P = PackedWords()
            sage: P()
            []
        """
        return super(SetPartitionIntoLists, self).__call__(x, *args, **keywords)

    def _element_constructor_(self, *args, **keywords):
        """
        EXAMPLES::

            sage: P = PackedWords()
            sage: P._element_constructor_()
            []
            sage: P()
            []
            sage: P([1,1,1])
            [1, 1, 1]
        """
        return self.element_class(self, *args, **keywords)

    def combinatorial_class_of_size(self, size):
        assert(size >= 0), "size (%d) must be a positive integer" % size
        return SetPartitionIntoLists(size)

    Element = SetPartitionIntoList


#==============================================================================
# Enumerated set of packed words of a given size
#==============================================================================
class SetPartitionIntoLists_size(SetPartitionIntoLists):
    """
    TESTS::

        sage: from sage.combinat.packed_words import PackedWords_size
        sage: for i in range(6): TestSuite(PackedWords_size(i)).run()

    """

    def __init__(self, size):
        super(SetPartitionIntoLists_size, self).__init__(
                category=FiniteEnumeratedSets())
        self._size = size

    def _repr_(self):
        """
        TESTS::

            sage: PackedWords(4)
            Packed words of size 4
        """
        return "Set Partition into List of size %s" % (self._size)

    def __contains__(self, x):
        """
        TESTS::

            sage: P = PackedWords(4)
            sage: 1 in P
            False
            sage: PackedWord([]) in P
            False
            sage: PackedWord([1,2,1,3,1,4]) in P
            False
            sage: PackedWord([1,2,1,3]) in P
            True
        """
        return isinstance(x, self.element_class) and x.size() == self._size

    def _an_element_(self):
        """
        TESTS::

            sage: PackedWords(6).an_element()
            [1, 2, 3, 4, 5, 6]
        """
        return self.first()

    def cardinality(self):
        """
        Stirling number ???

        TESTS::

            sage: from sage.combinat.packed_words import PackedWords_size
            sage: PackedWords_size(0).cardinality()
            1
            sage: PackedWords_size(1).cardinality()
            1
            sage: PackedWords_size(2).cardinality()
            3
            sage: PackedWords_size(3).cardinality()
            13
        """
        pass
        return OrderedSetPartitions(self._size).cardinality()

    def __iter__(self):
        """
        TESTS::

            sage: from sage.combinat.packed_words import PackedWords_size
            sage: list(PackedWords_size(0))
            [[]]
            sage: list(PackedWords_size(1))
            [[1]]
            sage: list(PackedWords_size(2))
            [[1, 2], [2, 1], [1, 1]]
            sage: list(PackedWords_size(3))
            [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1],
             [1, 2, 2], [2, 1, 2], [2, 2, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1],
             [1, 1, 1]]
        """
        from set_partition import SetPartitions
        for sp in SetPartitions(self._size):
            for p in CartesianProduct(*tuple(Permutations(list(b)).list() for b in sp)):
                yield self.element_class(self, p)
        # SPIL += [Set(map(tuple, l)) for l in c]

    @lazy_attribute
    def _parent_for(self):
        """
        The parent of the element generated by ``self`

        TESTS::

            sage: P = PackedWords(4)
            sage: P._parent_for
            Packed words
        """
        return SetPartitionIntoLists_all()

    @lazy_attribute
    def element_class(self):
        """
        TESTS::

            sage: P = PackedWords(4)
            sage: P.element_class
            <class 'sage.combinat.packed_words.PackedWords_all_with_category.element_class'>
            sage: P.first().__class__ == PackedWords().first().__class__
            True
        """
        return self._parent_for.element_class

    def _element_constructor_(self, *args, **keywords):
        """
        EXAMPLES::

            sage: P = PackedWords(0)
            sage: P([])
            []

            # sage: P([1])
            # Traceback (most recent call last)
            # ...
            # ValueError: Wrong size of word
        """
        res = self.element_class(self._parent_for, *args, **keywords)
        if res.size() != self._size:
            raise ValueError, "Wrong size of word"
        return res

    def permutation_to_packed_words(self, sigma):
        """
        Compute all packed words which give *sigma* by standardization.

        TESTS::

            sage: PW = PackedWords()
            sage: PW.permutation_to_packed_words(Permutation([3,1,2,4]))
            [[2, 1, 1, 2], [2, 1, 1, 3], [3, 1, 2, 3], [3, 1, 2, 4]]
            sage: PW.permutation_to_packed_words(Permutation([1,2,3]))
            [[1, 1, 1], [1, 1, 2], [1, 2, 2], [1, 2, 3]]
        """
        if self._size <= 1:
            if self._size == 0:
                return [self._element_constructor_([])]
            if self._size == 1:
                return [self._element_constructor_([1])]
        li = [({sigma.index(1):1}, sigma.index(1))]
        for i in range(2, self._size):
            index_i = sigma.index(i)
            tmp = []
            for (pw, l_index) in li:
                if l_index < index_i:
                    pw[index_i] = pw[l_index]
                    tmp.append((dict(pw), index_i))
                pw[index_i] = pw[l_index] + 1
                tmp.append((dict(pw), index_i))
            li = tmp
        index_i = sigma.index(self._size)
        res = []
        for (pw, l_index) in li:
            if l_index < index_i:
                pw[index_i] = pw[l_index]
                res.append(self._element_constructor_(pw.values()))
            pw[index_i] = pw[l_index] + 1
            res.append(self._element_constructor_(pw.values()))
        return res
